COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00011 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\font\rmn=cmr9

\line{\sevenrm a91.tex[106,phy] \today\hfill}

\medskip
\line{\bf Divide and Conquer\hfill}

\figbox 1.2truein:

\centerline{$\bullet$}
\centerline{$M$}

\medskip
Suppose we know the function $f$ has a unique local minimum~$M$, as shown
above. This means  if $A<B≤M$, $f(A)>f(B)$, and if $M≤C<D$, $f(C)<f(D)$.
We want an algorithm to find~$M$.

The divide-and-conquer heuristic breaks the problem into two easier problems:

\disleft 25pt:(1):
Find a finite interval certain to contain~$M$.
\disleft 25pt:(2):
Locate $M$ within such an interval.

\noindent
Now we look for a subalgorithm for subproblem~(1). It in turn breaks into
two subproblems.

\smallskip
\disleft 25pt:(1.1):
Find $P$ certain to be less than $M$.
\disleft 25pt:(1.2):
Find $Q$ certain to be greater than $M$.

\smallskip
By looking at points farther and farther to the left, $P↓1>P↓2>P↓3>\cdots$,
in an unbounded sequence, eventually some $P↓i<M$, and $P↓{i+1}<P↓i<M$,
so $f(P↓{i+1})>f(P↓i)$. On the other hand, if $f(P↓{j+1})>f(P↓j)$, it must
be true that $P↓{j+1}<M$. A~natural choice is $P↓i=-2↑i$; the 
subalgorithm~(1.1) is then:

\smallskip
\halign{\qquad\qquad{\tt #}\hfill\cr
P1:=-1;\cr
P:=-2;\cr
WHILE f(P)<=f(P1) DO\cr
\qquad BEGIN\cr
\qquad P1:=P;\cr
\qquad P:=2*P\cr
\qquad END;\cr
(* P<M *)\cr}

\smallskip\noindent
and by the obvious symmetry between (1.1) and (1.2), subalgorithm (1.2) is

\smallskip
\halign{\qquad\qquad{\tt #}\hfill\cr
Q1:=1;\cr
Q:=2;\cr
WHILE f(Q)<=f(Q1) DO\cr
\qquad BEGIN\cr
\qquad Q1:=Q;\cr
\qquad Q:=2*Q\cr
\qquad END;\cr
(* Q<M *)\cr}


\smallskip
Having solved problem~(1), we look at problem (2). As the graph below indicates,
no finite number of evaluations of~$f$ can indicate exactly where $M$ is.

$$\vcenter{\halign{\hfil${#}$\hfil\qquad%
&\hfil${#}$\hfil\qquad\qquad%
&\hfil${#}$\hfil\qquad\qquad\qquad%
&\hfil${#}$\hfil\qquad\qquad\qquad%
&\hfil${#}$\hfil\qquad\qquad\qquad%
&\hfil${#}$\hfil\cr
\bullet\cr
&&&&&\bullet\cr
&\bullet\cr
&&\bullet&&\bullet\cr
&&&\bullet\cr
\noalign{\smallskip}
\noalign{\hrule}
\noalign{\smallskip}
P↓1&P↓2&P↓3&P↓4&P↓5&P↓6\cr}}$$

\bigskip\noindent
It could be anywhere between $P↓3$ and $P↓5$, but not outside that interval.
This shows also that knowing $M$~lies in a particular interval, say
$(P↓3,P↓5)$, and evaluating~$f$ at a single point in that interval, 
like~$P↓4$, may not restrict the range where $M$~could be.

This suggests repeatedly narrowing the interval where $M$ is known to be,
with the lengths of the intervals approaching zero, by evaluating~$f$ at
two or more points inside the interval. 

If $f$ has been evaluated at $P↓1<P↓2<P↓3<\cdots P↓n$, and $f(P↓i)$ is the
smallest value ($n=6$, $i=4$ in the illustration), then we know~$M$ lies
in $(P↓{i-1},P↓{i+1})$; if $n≥4$, this narrows the range where $M$ is known
to be.

We can then solve subproblem (2) by repeatedly applying this subalgorithm to
narrow the range~$(P,Q)$:

\smallskip
{\obeylines\obeyspaces\let =\ \tt
        BEGIN
        P2:=(2*P+Q)/3;
        IF F(P)<=F(P2) THEN Q:=P2
        ELSE
           BEGIN
           P3:=(P+2*Q)/3;
           IF F(P3)>=F(Q) THEN P:=P3
           ELSE
              IF F(P2)<F(P3) THEN Q:=P3
              ELSE P:=P2
           END
        END
}

\smallskip\noindent
Because each execution reduces the size of $(P,Q)$ by at least one third, 
eventually $\left|Q-P\right|$ becomes as small as desired, and~$P$
(or~$Q$) is as close to~$M$ as desired.

The entire program:

\smallskip
{\obeylines\obeyspaces\let =\ \tt
        READ(ERROR)
        P1:=-1; P:=-2;
        WHILE F(P)<=F(P1) DO
           BEGIN P1:=P; P:=2*P
           END; (* P<M *)
        Q1:=1; Q:=2;
        WHILE F(Q)=F(Q1) DO
           BEGIN Q1:=Q; Q:=2*Q
           END; (* Q>M *)
        WHILE ABS(Q-P)>ERROR DO
           BEGIN
           P2:=(2*P+Q)/3;
           IF F(P)<=F(P2) THEN (* P2>M *) Q:=P2
           ELSE
              BEGIN
              P3:=(P+2*Q)/3;
              IF F(P3)>=F(Q) THEN (* P3<M *) P:=P3
              ELSE
              IF F(P2)<F(P3) THEN (* P3>M *) Q:=P3
              ELSE (* P2<M *) P:=P2
              END
           END;
        WRITE(P)
}

\smallskip
The program above is probably not the most efficient
that could have been designed. It is correct, though; it will eventually
halt, and will give a correct answer to the desired precision. There are
too many programs that give invalid answers at tremendous speed.
Whever possible, a~program should be developed by logical reasoning from
the known properties of the problem.

$$\hbox{\vrule
 \vbox{\hrule \kern6truept
 \hbox{ Only a computer program can make a million mistakes per second. }
 \kern6truept\hrule}\vrule}$$

\medskip
\line{\bf The Divide-and-Conquer Paradigm.\hfill}

A heuristic rule for solving a complicated problem is to try to divide it
into two or more simpler problems.


\bigskip
\line{\copyright 1985 Robert W. Floyd\hfill}
\line{First draft (not published) October 1, 1985;\hfill}
%revised: Date; subsequently revised.\hfill}

\bye